R*树优化
R树不足
- 当索引数据量增加时，R树的深度及索引空间的重叠都会增大，而查找总是从根节点开始向下搜索,直至找到适合插入的叶节点 。但是它查找所须访问的分枝数、节点数会相应增加，查找性能会急剧下降。它采用的是一种自上而下的搜索方案 , 但是这往往不能获得最为合适的节点.
- R树的主要目标是支持高效的查询处理, 而没有考虑对象的更新效率问题。
R树优化
局部优化
在分裂算法中加入周长与重叠面积作为判定指标.
选择子树时,非叶结点采用面积增量标准,而叶结点采用重叠增量标准.
整体优化
对于同一集合,随着插入顺序的不同.会得到不同的R树结构.随着新数据的插入,R树结构的合理性会降低.
R*树提出对索引中已有结点进行有选择的重新插入一次,来优化R树的数据结构.